package com.zlz.quicksort;

import com.zlz.util.LogFactory;

import java.util.Arrays;
import java.util.logging.Logger;

/**
 * 快排
 *
 * @author zhulinzhong
 * @date 2022-01-24 11:54:59
 */
public class BaseQuicksort {

    private static final Logger LOGGER = LogFactory.getGlobalLog();
    int steps = 0;

    public int sort(int[] arr, boolean log) {
        recurveSort(arr, 0, arr.length - 1, log);
        return steps;
    }

    /**
     * 排序方法
     *
     * @param arr   数组
     * @param left  左边界
     * @param right 右边界
     * @param log   是否打印日志
     */
    public void recurveSort(int[] arr, int left, int right, boolean log) {
        if (left >= right) {
            return;
        }
        int empty = left;
        int low = left;
        int height = right;
        int key = arr[low];
        steps++;

        // 打印日志
        if (log) {
            LOGGER.info("");
            LOGGER.info("第" + steps + "次排序："
                    + Arrays.toString(arr) + "\n"
                    + String.format("排序范围：（%s,%s）,基准数字：%s", left, right, key));
        }

        while (low < height) {

            // 从右往左
            while (low < height && arr[height] >= key) {
                height--;
            }
            if (low < height) {
                arr[empty] = arr[height];
                empty = height;

            }

            // 从左往右
            while (low < height && arr[low] <= key) {
                low++;
            }
            if (low < height) {
                arr[empty] = arr[low];
                empty = low;

            }

            arr[empty] = key;
            recurveSort(arr, left, low - 1, log);
            recurveSort(arr, low + 1, right, log);
        }
    }
}
